package J.算法.排序;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class sort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str ;
        while ((str=br.readLine())!= null){
            String[] strs = str.split(",");
            int[] nums = new int[strs.length];
            for (int i = 0;i< nums.length;i++){
                nums[i] = Integer.valueOf(strs[i]);
            }

            //bubbleSort(nums);
            //selectSort(nums);
            //insertSort(nums);
            //shellSort(nums);
           // quickSort(nums,0,nums.length-1);
            //mergeSort(nums,0,nums.length-1);
          //  bucketSort(nums);
            radixSort(nums);
            for (int num:nums){
                System.out.println(num);
            }
        }
    }

    public static void bubbleSort(int[] nums){
        int temp =0;
        boolean change = false;
        for (int i=0;i< nums.length-1;i++){
            for (int j = 0; j < nums.length-i-1; j++) {
                if(nums[j] > nums[j+1]){
                    change = true;
                    temp = nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1] = temp;
                }
            }
            if (!change){
                break;
            }
        }
    }

    /**
     * 思路：假设分组的第一个就是最小的 从前往后找最小的 交换
     * @param nums
     */
    public static void selectSort(int[] nums){

        for (int i = 1; i < nums.length; i++) {
            int minIndex = i-1;
            int temp = nums[minIndex];
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < temp){
                    minIndex = j;
                }

            }
            if (minIndex != i-1){
                nums[i-1] = nums[minIndex];
                nums[minIndex] = temp;
            }

        }

    }

    public static void insertSort(int[] nums){

        for (int i = 1; i < nums.length; i++) {

            for (int j = i; j < nums.length; j++) {
                int searchIndex = j-1;
                int insertVal = nums[j];

                while (searchIndex>=0 && insertVal < nums[searchIndex]){
                    nums[searchIndex+1] = nums[searchIndex];
                    searchIndex--;
                }

                nums[searchIndex+1] = insertVal;
            }

        }
    }

    public static void shellSort(int[] nums){

        for (int gap= nums.length/2;gap>0;gap /=2){
            for(int j= gap;j< nums.length;j++){

                int searchIndex = j;
                int temp = nums[j];

                while (searchIndex-gap>= 0 && nums[searchIndex-gap] > temp) {
                    nums[searchIndex ] = nums[searchIndex-gap];
                    searchIndex -= gap;

                }
                nums[searchIndex] = temp;
            }
        }

    }

    public static void quickSort(int[] nums,int start,int end){

        if (start <end){
            int base = nums[start];
            int low = start;
            int high = end;

            while (low <high){

                while (low < high && nums[high]>base){
                    high--;
                }
                nums[low] = nums[high];

                while (low < high && nums[low]<base){
                    low++;
                }
                nums[high] = nums[low];

            }
            nums[low] = base;
            quickSort(nums,start,low);
            quickSort(nums,low+1,end);
        }
    }


    public static void mergeSort(int[] nums,int left,int right){
        if (left<right){
            int mid = (left+right)/2;

            mergeSort(nums,left,mid);
            mergeSort(nums,mid+1,right);

            merge(nums,left,mid,right);
        }

    }
    public static void merge(int[] nums,int left,int mid,int right){
        int i = left;
        int j = mid+1;
        int index =0;
        int[] temp = new int[right-left+1];

        while (i<= mid && j<= right){
            if (nums[i]<nums[j]){
                temp[index++] = nums[i++];
            }else {
                temp[index++] = nums[j++];
            }
        }

        while (i<= mid){
            temp[index++] = nums[i++];
        }
        while (j<= right){
            temp[index++] = nums[j++];
        }

        int copyLeft = left;
        for (int num:temp){
            nums[copyLeft++] = num;
        }
    }

    /**
     * 桶排序
     */
    public static void bucketSort(int[] nums){

        int bucketNum = 10;
        int[][] bucket = new int[bucketNum][nums.length];
        //遍历 放到桶内
        for (int i = 0; i < nums.length; i++) {
            int belong = nums[i]/10;
            for (int j = 0; j < nums.length; j++) {
                if (bucket[belong][j] == 0){
                    bucket[belong][j]= nums[i];
                    break;
                }
            }

        }

        //桶内排序
        for (int i = 0; i < bucketNum; i++) {
            int end= 0;
            while (end < bucket[i].length && bucket[i][end] != 0){
                end++;
            }
            if (end <0){
                continue;
            }
            quickSort(bucket[i], 0,end-1);
        }

        int index =0;
        for (int i = 0; i < bucketNum; i++) {
            for (int j = 0; j < bucket[i].length; j++) {
                if (bucket[i][j] == 0){
                    break;
                }
                nums[index++] = bucket[i][j];
            }

        }
    }

    public static void radixSort(int[] nums){
        int[][] bucket = new int[10][nums.length];
        int[] bucketCount = new int[10];

        int Max = nums[0];
        for(int num:nums){
            if(num > Max){
                Max = num;
            }
        }
        int digit = (Max+"").length();

        for(int round = 0,n=1;round < digit;round++,n *= 10){
            //遍历存桶
            for(int num:nums){
                int digitNum = num/n%10;
                bucket[digitNum][bucketCount[digitNum]] = num;
                bucketCount[digitNum]++;
            }
            //放完之后，从桶中依次取出放回原数组
            int index= 0;
            for(int i=0;i<10;i++){
               if (bucketCount[i] ==0){
                   continue;
               }else {
                   for (int j=0;j<bucketCount[i];j++){
                       nums[index++] = bucket[i][j];
                   }
               }
               bucketCount[i] = 0;
            }
        }

    }

}
